package newcoder_exp.justPractise;
import java.util.*;
import org.junit.*;

public class NC157 {
    public int[][] foundMonotoneStack (int[] nums) {
        Stack<Integer> stack = new Stack<>();
        int len = nums.length;
        int[][] res = new int[len][2];
        for (int i = 0; i < len; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            res[i][0] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        stack.clear();
        for (int i = len - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] >= nums[i]) {
                stack.pop();
            }
            res[i][1] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(i);
        }
        return res;
    }
    
    @Test
    public void test() {
        int[] nums = new int[]{3,4,1,5,6,2,7};
        int[][] res=  foundMonotoneStack (nums);
        System.out.println(Arrays.deepToString(res));
    }
}
